package dichotomy.find.closed.elements;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Time 2020/1/15
 * @author 王光浩
 * @Need 给出一个升序整型数组，一个target和一个count，在升序数组中找出离target最近的count个数（该数-target的绝对值最小）
 *       如果左右两边两个数相同则选择下标最小的那个数。
 * @Thinking 使用二分法。先找出离target最近的哪个数，然后向两边扩展找出离target最近的count个数。
 *           复杂度分析：时间复杂度O（logn+x），空间复杂度O（1）
 */
public class MyMethodOne {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> result=new ArrayList<>();
        int later=arr.length-1;
        int previous=0;
        int mid=0;
        //找出离target最近的元素
        while(later>=previous) {
        	mid=previous+(later-previous)/2;
        	if(arr[mid]==x)
        		break;
        	if(arr[mid]>x)
        		later=mid-1;
        	else 
        		previous=mid+1;
        }
        if(arr[mid]!=x) {//将最接近x的下标赋给mid
        	if(later==-1)mid=0;
        	else if(previous==arr.length)mid=arr.length-1;
        	else mid=(Math.abs(x-arr[later])>Math.abs(x-arr[previous])?previous:later);
        }
        //将最接近x的k个数加入到result集中
        later=mid+1;
        previous=mid-1;
        k--;
        result.add(arr[mid]);
        while(k>0) {
        	if(previous==-1)result.add(arr[later++]);
        	else if(later==arr.length)result.add(0,arr[previous--]);
        	else if(Math.abs(x-arr[previous])>Math.abs(x-arr[later]))
        		result.add(arr[later++]);
        	else
        		result.add(0, arr[previous--]);
        	k--;
        }
        return result;
    }

}
